package algorithm.array;

/**
 * leetcode : https://leetcode.com/problems/trapping-rain-water/
 * Difficulty : Hard
 * Topics : Array TwoPointers
 *
 * 接雨水.
 * 给一个非负的数组，数组中每个数字表示柱子高度，横坐标单位为1。问这些柱子可以在二维平面上接多少雨水
 *
 * Created by yzy on 2019-10-11 14:33
 */
public class TrappingRainWater {

    public static void main(String[] args) {
        int[] arr = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};     // output=6
        System.out.println(trap_1(arr));
    }


    /**
     * 暴力解法。
     * 只要算出每一个柱子顶部可以容纳的水的体积求和即可，那体积就是当前柱子和两边最高的那个差值
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     *
     * RunTime: 65ms, faster than 5.12%
     * Memory:  41.6MB, less than 5.48%
     *
     * @param height
     * @return
     */
    public static int trap_1(int[] height) {
        int trap = 0;
        for(int i=1; i<height.length-1; i++){
            int h = height[i];
            int max_l = 0;  // 左边最高的柱子
            int max_r = 0;  // 右边最高的柱子
            for(int t=0; t <height.length; t++){
                if(t==i){
                    continue;
                }
                if(t<i){
                    max_l = max_l > height[t] ? max_l : height[t];
                }else{
                    max_r = max_r > height[t] ? max_r : height[t];
                }
            }

            // 两边最高的柱子中，取低的那个。就是当前柱子水可以达到的最高高度
            int min_h = max_l > max_r ? max_r : max_l;
            if(min_h > h){
                trap = trap + (min_h - h);
            }
        }
        return trap;
    }


    /**
     * 优化，遍历一遍记录每一个index的左右边最高数字，再遍历一遍计算即可
     * 时间复杂度：O(1)
     * 空间复杂度：O(N)
     * @param height
     * @return
     */
    public static int trap_2(int[] height){
        int trap = 0;
        int[] max_l_arr = new int[height.length];
        int[] max_r_arr = new int[height.length];
        int range = height.length-1;
        int max_l = height[0];
        int max_r = height[range];
        for(int i=0; i<=range; i++){
            if(i==0 || i==range){
                max_l_arr[i] = 0;
                max_l_arr[i] = 0;
                continue;
            }

        }
        return trap;
    }
}
